package com.lun.medium;

import java.util.LinkedList;
import java.util.Queue;

import com.lun.util.BinaryTree.TreeNode;

public class FindBottomLeftTreeValue {
	
	//方法一：BFS
    public int findBottomLeftValue(TreeNode root) {
        
    	LinkedList<TreeNode> queue = new LinkedList<>();
    	queue.offer(root);
    	
    	TreeNode leftmost = null;
    	
    	while(!queue.isEmpty()) {
    		
    		int originalSize = queue.size();
    		for(int size = originalSize; size > 0; size--) {
    			TreeNode node = queue.poll();
    			
    			if(size == originalSize)
    				leftmost = node;
    			
    			if(node.left != null)
    				queue.offer(node.left);
    			if(node.right != null)
    				queue.offer(node.right);
    		}
    		
    	}
    	
    	return leftmost.val;
    }
    
    //方法二：BFS，比方法一更简洁
    public int findBottomLeftValue2(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            root = queue.poll();
            
            //从 右子树 到 左子树
            if (root.right != null)
                queue.add(root.right);
            if (root.left != null)
                queue.add(root.left);
        }
        return root.val;
    }
    
    //方法三：DFS
    public int findBottomLeftValue3(TreeNode root) {
    	int[] leftmost = {0}, depth = {0};
    	findBottomLeftValue3(root, 1, leftmost, depth);
    	return leftmost[0];
    }
    
    
    private void findBottomLeftValue3(TreeNode node, int height, int[] leftmost, int[] depth) {
    	if(node == null) return;
    	
    	if(height > depth[0]) {
    		leftmost[0] = node.val;
    		depth[0] = height;
    	}
    	
    	findBottomLeftValue3(node.left, height + 1, leftmost, depth);
    	findBottomLeftValue3(node.right, height + 1, leftmost, depth);
    }
    
    
}
